package com.dzu.medium;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ZhaoDong
 * @date 2022/12/5 9:44
 * @description 670. 最大交换
 */
public class Test670 {
    public static void main(String[] args) {
//        System.out.println(maximumSwap(98368));
//        System.out.println(maximumSwap(115));
//        System.out.println(maximumSwap(2736));
//        System.out.println(maximumSwap(1993));

        System.out.println(maximumSwap2(7326));

    }

    public static int maximumSwap2(int num) {
        List<Integer> list = new ArrayList<>();
        while (num != 0) {
            list.add(num % 10);
            num /= 10;
        }
        int n = list.size(), ans = 0;

        // idx[i]的含义：list中从索引0开始到i组成的子数组中值最大的索引
        int[] idx = new int[n];

        for (int i = 0, j = 0; i < n; i++) {
            if (list.get(i) > list.get(j)) {
                j = i;
            }
            idx[i] = j;
        }

        for (int i = n - 1; i >= 0; i--) {
            if (!list.get(idx[i]).equals(list.get(i))) {
                int c = list.get(idx[i]);
                list.set(idx[i], list.get(i));
                list.set(i, c);
                break;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            ans = ans * 10 + list.get(i);
        }
        return ans;


    }

    // 84 / 112 fail
    public static int maximumSwap(int num) {
        int[] arr = new int[10];
        Arrays.fill(arr, -1);
        int index = 9;
        while (num > 0) {
            arr[index--] = num % 10;

            num /= 10;
        }

        int pre = 10;
        for (int i = 0; i < arr.length; i++) {

            int s = arr[i];
            if (s == -1) {
                continue;
            }
            if (s >= pre) {
                int temps = s;
                int tempI = i;
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[j] >= s) {
                        temps = arr[j];
                        tempI = j;
                    }
                }
                arr[i - 1] = temps;
                arr[tempI] = pre;
                break;

            } else {
                pre = s;
            }

        }


        int resp = 0;
        for (int i : arr) {
            if (i == -1) {
                continue;
            }
            resp = resp * 10 + i;

        }

        return resp;


    }
}
